1. Field of the invention
This invention relates to an AND array architecture that enables efficient allocation of logic resources under varying functional requirements.
2. Related Art
Programmable logic devices (PLDs) are user configurable integrated circuits (ICs) that implement digital logic functions. One type of PLD, a programmable logic array (PLA) includes a combinatorial, two-level AND-OR structure that can be programmed to implement sum-of-products logic expressions.
FIG. 1a shows a conventional PLA 100 comprising an AND array 101 and an OR array 140. AND array 101 comprises pterm generators 120a-120h, each of which comprises one of a plurality of logic input lines Ia-Ih, and one of AND gates 110a-110h. Note that each of logic input lines Ia-Ih actually represents a set of logic input lines, but is depicted as a single line in FIG. 1a for clarity. While eight individual pterm generators are depicted in FIG. 1a, any number could be used in an actual PLD AND array. AND array 101 is coupled to receive input signals d1-d8 on a plurality of PLD input lines 130, which are formed perpendicular to logic input lines Ia-Ih, thereby creating a grid formation. The PLD input lines and logic input lines are programmably interconnected, wherein electrical connections can be defined at any of the intersections in the grid. The electrical connections can be one-time programmable (e.g., fusible link or antifuse technology), or reprogrammable (e.g., SRAM-based configuration). In FIG. 1a, an xe2x80x9cXxe2x80x9d is shown at each intersection at which an electrical connection is present. This programmed interconnect matrix therefore routes input signals d1-d8 among pterm generators 120a-120h according to the desired function of PLA 100. Pterm generators 120a-120h perform logical AND operations on incoming signals d1-d8 using AND gates 110a-110h, respectively, and provide product terms Pa-Ph, respectively, to OR array 120.
OR array 140 comprises an OR gate 141 coupled to receive pterms Pa-Pd, and an OR gate 142 coupled to receive pterms Pe-Ph. OR gates 141 and 142 perform logical OR operations on their respective pterms, thereby producing the sum-of-products expressions X and Y, respectively. Note that although two OR gates are shown in FIG. 1a, any number of OR gates with any number of inputs could be included in an actual PLD OR array.
OR array 140 further comprises a return line 143, which allows the output of OR gate 142 to be connected to an input terminal of OR gate 141. As shown in FIG. 1a, return line 143 is connected to the output of OR gate 142 and ground through an NMOS pass transistor 144 and a PMOS pass transistor 145, respectively. One of pass transistors 144 and 145 is conducting, and the other is nonconducting, in response to a control signal CONTROL. When control signal CONTROL is in a logic LOW state, return line 143 is connected to ground, and does not affect the operation of OR gate 141. However, when an OR operation must be performed on a quantity of pterms that exceed the number of input terminals of OR gate 141 (four, in this case, since one input terminal must be dedicated to return line 143), pass transistor 144 is turned on by a logic HIGH control signal CONTROL. As shown in FIG. 1a, AND array 101 has been programmed to perform the following logical operations:
Because OR gate 141 only has five input terminals, it cannot perform a logical OR operation on more that number of output pterms from AND array 101, as would be required for the following PLD operation:
X=d1xc2x7d2+d3xc2x7d4+d5xc2x7d6+d7xc2x7d8+d1xc2x7d4+d5xc2x7d8xe2x80x83xe2x80x83[1]
To enable such an operation, OR gate 141 must xe2x80x9cborrowxe2x80x9d some logic from OR gate 142. This logic sharing is performed through return line 143. In other words, OR gate 142 performs the operation:
Y=d7xc2x7d8+d1xc2x7d4+d5xc2x7d8xe2x80x83xe2x80x83[2]
This result is then coupled, through return line 143, to an input of OR gate 141, which then performs the logical operation:
xe2x80x83X=d1xc2x7d2+d3xc2x7d4+d5xc2x7d6+(d7xc2x7d8+d1xc2x7d4+d5xc2x7d8)xe2x80x83xe2x80x83[3]
which, by the transitive property resolves to the desired operation [1], i.e.,:
X=d1xc2x7d2+d3xc2x7d4+d5xc2x7d6+d7xc2x7d8+d1xc2x7d4+d5xc2x7d8
This xe2x80x9clogic sharingxe2x80x9d technique, while enabling the implementation of more complex logical functions than would otherwise be possible, leads to substantial inefficiency in the use of the logic resources in a PLD. Because one of the input terminals of each OR gate must be dedicated to the return line from another OR gate, that logic is wasted when the return line is not used. In addition, the xe2x80x9cloopingxe2x80x9d of output signals from one OR gate to the input of another OR gate undesirably decreases the speed of the PLD, due to the serial nature of the operation.
As the borrowed logic (i.e., the number of adjacent OR gates that must be coupled to the input terminals of the original OR gate) increases, this looping delay also increases. This inefficiency can be significantly magnified in a large-scale, or complex PLD (CPLD) that is configured to perform a complex logical operation.
Inefficient use of logic resources in a conventional PLD also arises within the individual pterm generators. Because each pterm generator 120 includes a single AND gate with several input terminals, simple logical AND operations (e.g., a two variable AND operation) result in non-use of all the logic associated with the other AND inputs. FIG. 1b illustrates a more detailed diagram of pterm generator 120a, including logic input lines Ia1-Ia8 (logic input line Ia in FIG. 1a) coupled to the input terminals of AND gate 110a. PLD input lines 130 are formed perpendicular to logic input lines Ia1-Ia8 in a grid formation with programmable interconnections at the intersections of these two sets of lines, thereby enabling input signals d1-d8 to be selectively provided to AND gate 110a. An xe2x80x9cXxe2x80x9d at a particular grid intersection indicates the presence of a conductive link.
Because AND gate 110a includes a large number of logic input lines Ia, it is sometimes referred to as a xe2x80x9cwide AND gate.xe2x80x9d Typical PLAs use wide AND gates to simplify the AND array layout. Consequently, implementation of simple functions in such PLDs wastes much of the available AND logic. For example, as depicted in FIG. 1b, pterm generator 120a is configured to perform the following operation:
Pa=d1xc2x7d2xe2x80x83xe2x80x83[4]
As shown in FIG. 1b , this function can be implemented by programming logic input lines Ia1 and Ia2 to receive input signals d1 and d2. The remaining logic input lines Ia3-Ia8 and their associated logic within wide AND gate 110a are not necessary to implement two-term AND function [4]. At the same time, because it is integrated in wide AND gate 110a, this unused logic cannot be shared with any other functions being programmed into the overall PLD. Therefore, the implementation of simple AND functions in conventional PLDs is extremely wasteful.
Accordingly, it is desirable to provide an architecture that maximizes the utilization of the available logic in a PLD without adversely affecting PLD performance.
The present invention provides a xe2x80x9cscalable pterm generatorxe2x80x9d that beneficially enhances the logic-handling capability of an IC. Scalable pterm generators can be used in place of conventional pterm generators in the AND array of a PLA to improve the programmability and utility of the PLA. A scalable pterm generator comprises a selective logic circuit that includes both the wide AND logic of a conventional pterm and alternative logic that includes OR logic. The alternative logic advantageously enables more efficient implementation of functions that do not require the full wide AND logic (i.e., functions in which the AND operations are performed on fewer terms than the number of inputs to the wide AND gate). At the same time, the wide AND logic is still available if required.
According to an embodiment of the present invention, a scalable pterm generator comprises a wide AND gate, an alternative logic circuit, a set of logic input lines, and an output control circuit. Each of the logic input lines feeds into an input terminal of the wide AND gate and an input terminal of the alternative logic circuit. The output control circuit is coupled to receive the output signals of the wide AND gate and the alternative logic circuit and provide a selected one of the output signals as a final output signal of the scalable pterm generator. In a PLA, the PLD input lines are programmably interconnected with the logic input lines of the scalable pterm generator, using either one-time programmable or reprogrammable technology. PLD input signals on the PLD input line array can then be selectively provided to the logic input lines of the scalable pterm generator, which feeds those signals to both the wide AND gate and the alternative logic circuit.
The alternative logic circuit is configured to perform a logical operation that is different than the AND operation performed by the wide AND gate. Therefore, the alternative logic circuit includes at least one OR gate. In an embodiment of the present invention, the alternative logic circuit comprises a plurality of secondary AND gates, each of the secondary AND gates having fewer input terminals than the wide AND gate. Each of the logic input lines is connected to an input terminal of one of the secondary AND gates, and the output terminals of the secondary AND gates feed into the input terminals of an OR gate. The output of the OR gate then becomes the output of the alternative logic circuit. Factors that influence the number of secondary AND gates, and the number of input terminals in each of those secondary AND gates, include the number of input terminals in the wide AND gate and the expected usage of the PLD.
The output control circuit can comprise any circuit for selecting a single output from multiple sources, such as a programmable routing circuit or a multiplexer. According to an embodiment of the present invention, the output control circuit comprises a conductive line that is programmably connected to the output terminals of the wide AND gate and the alternative logic circuit. During programming of the PLD, the conductive line can also be programmed to define the final scalable pterm generator output. According to another embodiment of the present invention, the output control circuit comprises a first pass transistor formed in-line with the output of the wide AND gate, and a second pass transistor formed in-line with the output of the alternative logic circuit. An inverter coupled to receive a control signal is connected to the gate of one of the pass transistors, and the control signal is directly coupled to the gate of the other pass transistor. The control signal therefore controls the source of the scalable pterm generator output.
According to another embodiment of the present invention, the scalable pterm generator comprises xe2x80x9cintegratedxe2x80x9d alternative logic. A multi-stage configuration is used, wherein the full wide AND logic is carried out in stages by a plurality of smaller AND gates. Each xe2x80x9cstagexe2x80x9d comprises a set of the smaller AND gates configured to perform their AND operations in parallel. The input terminals of the AND gates in a particular stage are fed by the output terminals of the AND gates in the previous stage, with the input terminals of the AND gates in the first stage being coupled to the logic input lines. The final stage comprises a single AND gate, the multi-stage configuration of AND gates thereby providing the desired wide AND functionality.
The alternative logic is integrated into the scalable pterm generator by coupling the input terminals of an OR gate to the output terminals of one of the AND stages. Because the alternative logic is integrated into the wide AND logic, the need for dedicated AND logic to accompany the OR gate is eliminated. According to an embodiment of the present invention, a single OR gate is integrated with the outputs of a single stage. According to another embodiment of the present invention, the scalable pterm generator comprises multiple OR gates, each OR gate being integrated with the outputs of a different stage. The output terminal(s) of the OR gate(s) and the output terminal of the final AND stage are fed into an output control circuit, which provides a selected one of its inputs as the final output of the scalable pterm generator. As described previously, the output control circuit can comprise either a programmable circuit or a controllable circuit.
The present invention will be more fully understood in view of the following description and drawings.